// Randomized Quick Sort.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include "time.h"

using namespace std;

template <typename T>
void swap_t( T &a, T &b) {
	T tmp;
	tmp = a;
	a = b;
	b = tmp;
}

void randomize( vector<int> &orig,int p, int r) {
	int i;
	srand( (unsigned)time(NULL));
	i = rand() % (r-p+1) + p;
	swap_t<int>(orig[i], orig[r]);
	return;
}

int Randomized_Partition( vector<int> &orig, int p, int r) {
	randomize(orig,p,r);
	int i,j,x;
	x = orig[r];
	i = p-1;
	for ( j = p; j < r; ++ j) {
		if ( orig[j] <= x ) {
			++ i;
			swap_t<int>(orig[i],orig[j]);
		}
	}
	swap_t<int>(orig[i+1],orig[r]);
	return (i+1);
}

void QuickSort( vector<int> &orig, int p, int r ) {
	int q;
	if ( p < r ) {
		q = Randomized_Partition(orig,p,r);
		QuickSort(orig,p,q-1);
		QuickSort(orig,q+1,r);
	}else
		return;
}

int _tmain()
{
	int buffer;
	vector<int> A;
	cout << "please input an array of numbers." << endl;
	while(cin >> buffer)
		A.push_back(buffer);
	QuickSort(A,0,A.size()-1);
	for ( vector<int> :: iterator ivec = A.begin(); ivec != A.end(); ++ ivec)
		cout << *ivec << "\t";
	cout << endl;
	return 0;
}

